/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.

This file is part of Quake III Arena source code.

Quake III Arena source code is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.

Quake III Arena source code is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Foobar; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
*/


#include "qbsp.h"
#include "../common/aselib.h"


#define MAX_FOLIAGE_MODELS		0x400

typedef struct {
	char		model[256];

	int			numSurfaces;

	float		radius[MD3_MAX_SURFACES];

	int			shader[MD3_MAX_SURFACES];
	shaderInfo_t	*shaderInfo[MD3_MAX_SURFACES];

	int			firstIndex[MD3_MAX_SURFACES];
	int			numIndices[MD3_MAX_SURFACES];

	int			firstVertex[MD3_MAX_SURFACES];
	int			numVertices[MD3_MAX_SURFACES];

	int			firstNeighbor[MD3_MAX_SURFACES];
	int			firstFacePlane[MD3_MAX_SURFACES];
} foliageModel_t;

static int				numMapFoliageModels;
static foliageModel_t	mapFoliageModels[MAX_FOLIAGE_MODELS];


extern md3Header_t	*LoadModel(const char *modelName);

extern void			BuildSurfaceTriangleNeighbors (int numTriangles, int *indices, int *neighbors);
extern void			CalcSurfaceTangentVectors (int numIndices, int *indices, int numVertices, drawVertNew_t *vertices);
extern void			CalcSurfaceFacePlanes (int numTriangles, int *indices, dplane_t *facePlanes, drawVertNew_t *vertices);


static void EmitFoliageModelIndices (int numTriangles, md3Triangle_t *triangles, foliageModel_t *fm, int num){

	int		i;

	fm->firstIndex[num] = numDrawIndexes;
	fm->numIndices[num] = numTriangles * 3;

	for (i = 0; i < numTriangles; i++){
		if (numDrawIndexes + 3 > MAX_MAP_DRAW_INDEXES)
			Error("MAX_MAP_DRAW_INDEXES");

		drawIndexes[numDrawIndexes++] = triangles[i].indexes[0];
		drawIndexes[numDrawIndexes++] = triangles[i].indexes[1];
		drawIndexes[numDrawIndexes++] = triangles[i].indexes[2];
	}

	// Compute neighbors
	fm->firstNeighbor[num] = fm->firstIndex[num];

	if (numDrawNeighbors + fm->numIndices[num] > MAX_MAP_DRAW_NEIGHBORS)
		Error("MAX_MAP_DRAW_NEIGHBORS");

	BuildSurfaceTriangleNeighbors(fm->numIndices[num] / 3, &drawIndexes[fm->firstIndex[num]], &drawNeighbors[fm->firstNeighbor[num]]);
	numDrawNeighbors += fm->numIndices[num];
}

static qboolean InsertMD3FoliageModel (foliageModel_t *fm){

	md3Header_t			*md3;
	md3Surface_t		*surface;
	md3Shader_t			*shader;
	md3Triangle_t		*triangle;
	md3St_t				*st;
	md3XyzNormal_t		*xyzNormal;
	drawVertNew_t		*outVert;
	char				name[256];
	vec3_t				mins, maxs;
	float				lat, lng;
	int					i, j;

	md3 = LoadModel(fm->model);
	if (!md3)
		return qfalse;

	fm->numSurfaces = md3->numSurfaces;

	// Each MD3 surface will become a foliage surface
	surface = (md3Surface_t *)((byte *)md3 + md3->ofsSurfaces);

	for (i = 0; i < md3->numSurfaces; i++){
		ClearBounds(mins, maxs);

		// Emit the shader
		shader = (md3Shader_t *)((byte *)surface + surface->ofsShaders);

		strcpy(name, shader->name);
		StripExtension(name);
		fm->shader[i] = EmitShader(name);
		fm->shaderInfo[i] = ShaderInfoForShader(name);

		// Emit the indices
		triangle = (md3Triangle_t *)((byte *)surface + surface->ofsTriangles);

		EmitFoliageModelIndices(surface->numTriangles, triangle, fm, i);

		// Emit the vertices
		fm->firstVertex[i] = numDrawVerts;
		fm->numVertices[i] = surface->numVerts;

		st = (md3St_t *)((byte *)surface + surface->ofsSt);
		xyzNormal = (md3XyzNormal_t *)((byte *)surface + surface->ofsXyzNormals);

		for (j = 0; j < surface->numVerts; j++, st++, xyzNormal++){
			if (numDrawVerts == MAX_MAP_DRAW_VERTS)
				Error("MAX_MAP_DRAW_VERTS");

			outVert = &drawVerts[numDrawVerts++];

			outVert->xyz[0] = MD3_XYZ_SCALE * xyzNormal->xyz[0];
			outVert->xyz[1] = MD3_XYZ_SCALE * xyzNormal->xyz[1];
			outVert->xyz[2] = MD3_XYZ_SCALE * xyzNormal->xyz[2];

			outVert->st[0] = st->st[0];
			outVert->st[1] = st->st[1];

			outVert->color[0] = 255;
			outVert->color[1] = 255;
			outVert->color[2] = 255;
			outVert->color[3] = 255;

			// Decode the normal
			lat = (xyzNormal->normal >> 8) & 0xFF;
			lng = (xyzNormal->normal >> 0) & 0xFF;

			lat *= Q_PI/128;
			lng *= Q_PI/128;

			outVert->normal[0] = cos(lat) * sin(lng);
			outVert->normal[1] = sin(lat) * sin(lng);
			outVert->normal[2] = cos(lng);

			// Add to bounds
			AddPointToBounds(outVert->xyz, mins, maxs);
		}

		// Compute radius for culling
		fm->radius[i] = RadiusFromBounds(mins, maxs);

		// Compute face planes
		fm->firstFacePlane[i] = numFacePlanes;

		if (numFacePlanes + fm->numIndices[i]/3 > MAX_MAP_DRAW_FACEPLANES)
			Error("MAX_MAP_DRAW_FACEPLANES");

		CalcSurfaceFacePlanes(fm->numIndices[i] / 3, &drawIndexes[fm->firstIndex[i]], &facePlanes[fm->firstFacePlane[i]], &drawVerts[fm->firstVertex[i]]);
		numFacePlanes += fm->numIndices[i] / 3;

		// Compute tangent vectors
		CalcSurfaceTangentVectors(fm->numIndices[i], &drawIndexes[fm->firstIndex[i]], fm->numVertices[i], &drawVerts[fm->firstVertex[i]]);

		if (fm->numIndices[i] > SHADER_MAX_INDEXES || fm->numVertices[i] > SHADER_MAX_VERTEXES)
			Error("SHADER_MAX_INDEXES or SHADER_MAX_VERTEXES hit by foliage surface with shader %s", name);

		// Find the next surface
		surface = (md3Surface_t *)((byte *)surface + surface->ofsEnd);
	}

	return qtrue;
}

static qboolean InsertASEFoliageModel (foliageModel_t *fm){
	int					i, j, l;
	mapDrawSurface_t	*out;
	int					numSurfaces;
	const char			*name;
	polyset_t			*pset;
	int					numFrames;
	char				filename[1024];
	char				material[256];

	drawVertNew_t		*outVert;
	vec3_t				mins, maxs;

	int					indexList[SHADER_MAX_INDEXES];
	int					numIndices;

	drawVert_t			vertexList[SHADER_MAX_VERTEXES], vertex;
	int					numVertices;

	sprintf( filename, "%s%s", gamedir, fm->model );

	// load the model
	ASE_Load( filename, qfalse, qfalse );

	// each ase surface will become a new bsp surface
	numSurfaces = ASE_GetNumSurfaces();
	if (numSurfaces > MD3_MAX_SURFACES)
		Error("MD3_MAX_SURFACES");

	fm->numSurfaces = numSurfaces;

	// expand, translate, and rotate the vertexes
	// swap all the surfaces
	for ( i = 0 ; i < numSurfaces ; i++) {
		ClearBounds(mins, maxs);

		name = ASE_GetSurfaceName( i );

		pset = ASE_GetSurfaceAnimation( i, &numFrames, -1, -1, -1 );
		if ( !name || !pset ) {
			continue;
		}

		// Emit the shader
		strcpy(name, pset->materialname);
		StripExtension(name);
		fm->shader[i] = EmitShader(name);
		fm->shaderInfo[i] = ShaderInfoForShader(name);

		// Copy vertices
		numIndices = 0;
		numVertices = 0;

		for ( j = 0 ; j < pset->numtriangles * 3 ; j++ ) {
			int		index;
			triangle_t	*tri;

			index = j % 3;
			tri = &pset->triangles[ j / 3 ];

			vertex.st[0] = tri->texcoords[index][0];
			vertex.st[1] = tri->texcoords[index][1];

			vertex.xyz[0] = tri->verts[index][0];
			vertex.xyz[1] = tri->verts[index][1];
			vertex.xyz[2] = tri->verts[index][2];

			vertex.color[0] = (byte)(255.0f * tri->colors[index][0]);
			vertex.color[1] = (byte)(255.0f * tri->colors[index][1]);
			vertex.color[2] = (byte)(255.0f * tri->colors[index][2]);
			vertex.color[3] = 255;

			// Add it to the vertex list if not added yet
			if (numIndices == SHADER_MAX_INDEXES){
				printf("SHADER_MAX_INDEXES hit\n");
				return qfalse;
			}

			for (l = 0; l < numVertices; l++){
				if (vertexList[l].xyz[0] != vertex.xyz[0] || vertexList[l].xyz[1] != vertex.xyz[1] || vertexList[l].xyz[2] != vertex.xyz[2])
					continue;
				if (vertexList[i].st[0] != vertex.st[0] || vertexList[i].st[1] != vertex.st[1])
					continue;

				break;
			}

			if (l == numVertices){
				if (numVertices == SHADER_MAX_VERTEXES){
					printf("SHADER_MAX_VERTEXES hit\n");
					return qfalse;
				}

				indexList[numIndices++] = numVertices;
				vertexList[numVertices++] = vertex;
			}
			else
				indexList[numIndices++] = l;
		}

		// Emit the indices
		fm->firstIndex[i] = numDrawIndexes;
		fm->numIndices[i] = numIndices;

		for (j = 0; j < numIndices; j += 3){
			if (numDrawIndexes + 3 > MAX_MAP_DRAW_INDEXES)
				Error("MAX_MAP_DRAW_INDEXES");

			drawIndexes[numDrawIndexes++] = indexList[j+0];
			drawIndexes[numDrawIndexes++] = indexList[j+1];
			drawIndexes[numDrawIndexes++] = indexList[j+2];
		}

		// Compute neighbors
		fm->firstNeighbor[i] = fm->firstIndex[i];

		if (numDrawNeighbors + fm->numIndices[i] > MAX_MAP_DRAW_NEIGHBORS)
			Error("MAX_MAP_DRAW_NEIGHBORS");

		BuildSurfaceTriangleNeighbors(fm->numIndices[i] / 3, &drawIndexes[fm->firstIndex[i]], &drawNeighbors[fm->firstNeighbor[i]]);
		numDrawNeighbors += fm->numIndices[i];

		// Emit the vertices
		fm->firstVertex[i] = numDrawVerts;
		fm->numVertices[i] = numVertices;

		for (j = 0; j < numVertices; j++){
			if (numDrawVerts == MAX_MAP_DRAW_VERTS)
				Error("MAX_MAP_DRAW_VERTS");

			outVert = &drawVerts[numDrawVerts++];

			outVert->xyz[0] = vertexList[j].xyz[0];
			outVert->xyz[1] = vertexList[j].xyz[1];
			outVert->xyz[2] = vertexList[j].xyz[2];

			outVert->st[0] = vertexList[j].st[0];
			outVert->st[1] = vertexList[j].st[1];

			outVert->color[0] = vertexList[j].color[0];
			outVert->color[1] = vertexList[j].color[1];
			outVert->color[2] = vertexList[j].color[2];
			outVert->color[3] = vertexList[j].color[3];
		}

		// Compute radius for culling
		fm->radius[i] = RadiusFromBounds(mins, maxs);

		// Compute face planes
		fm->firstFacePlane[i] = numFacePlanes;

		if (numFacePlanes + fm->numIndices[i]/3 > MAX_MAP_DRAW_FACEPLANES)
			Error("MAX_MAP_DRAW_FACEPLANES");

		CalcSurfaceFacePlanes(fm->numIndices[i] / 3, &drawIndexes[fm->firstIndex[i]], &facePlanes[fm->firstFacePlane[i]], &drawVerts[fm->firstVertex[i]]);
		numFacePlanes += fm->numIndices[i] / 3;

		// Compute tangent vectors
		CalcSurfaceTangentVectors(fm->numIndices[i], &drawIndexes[fm->firstIndex[i]], fm->numVertices[i], &drawVerts[fm->firstVertex[i]]);

		if (fm->numIndices[i] > SHADER_MAX_INDEXES || fm->numVertices[i] > SHADER_MAX_VERTEXES)
			Error("SHADER_MAX_INDEXES or SHADER_MAX_VERTEXES hit by foliage surface with shader %s", name);
	}

	return qtrue;
}

static qboolean InsertLWOFoliageModel (foliageModel_t *fm){

	lwObject			*inObject;
	lwLayer				*inLayer;
	lwSurface			*inSurface;
	lwPolygon			*inPolygon;
	lwPolVert			*inPolVert;
	lwPoint				*inPoint;
	lwVMapPt			*inVMapPt;
	mapDrawSurface_t	*out;
	char				name[256];
	int					defaultSTAxis[2];
	float				defaultXYZ2STScale[2];
	float				min, max, size, st[2];
	unsigned			failId;
	int					failPos;
	int					i, j, k, l;

	drawVertNew_t		*outVert;
	vec3_t				mins, maxs;

	int					indexList[SHADER_MAX_INDEXES];
	int					numIndices;

	drawVert_t			vertexList[SHADER_MAX_VERTEXES], vertex;
	int					numVertices;

	char				filename[1024];

	sprintf( filename, "%s%s", gamedir, fm->model );

	// Load the file
	inObject = lwGetObject(filename, &failId, &failPos);
	if (!inObject)
		return qfalse;

	if (inObject->nlayers != 1){
		printf("LWO has invalid number of layers (%i)\n", inObject->nlayers);
		return qfalse;
	}

	if (inObject->nsurfs > MD3_MAX_SURFACES)
		Error("MD3_MAX_SURFACES");

	inLayer = &inObject->layer[0];

	// Setup default ST map
	defaultSTAxis[0] = 0;
	defaultSTAxis[1] = 1;

	st[0] = 0.0f;
	st[1] = 0.0f;

	for (i = 0; i < 3; i++){
		min = inLayer->bbox[i+0];
		max = inLayer->bbox[i+3];

		size = max - min;

		if (size > st[0]){
			defaultSTAxis[1] = defaultSTAxis[0];
			defaultSTAxis[0] = i;

			st[1] = st[0];
			st[0] = size;
		}
		else if (size > st[1]){
			defaultSTAxis[1] = i;

			st[1] = size;
		}
	}

	defaultXYZ2STScale[0] = 4.0f / st[0];
	defaultXYZ2STScale[1] = 4.0f / st[1];

	// Each LWO surface will become a new BSP surface
	inSurface = inObject->surf;

	fm->numSurfaces = inObject->nsurfs;

	for (i = 0; i < inObject->nsurfs; i++){
		ClearBounds(mins, maxs);

		// Emit the shader
		strcpy(name, inSurface->name);
		StripExtension(name);
		fm->shader[i] = EmitShader(name);
		fm->shaderInfo[i] = ShaderInfoForShader(name);

		// Copy vertices
		numIndices = 0;
		numVertices = 0;

		for (j = 0, inPolygon = inLayer->polygon.pol; j < inLayer->polygon.count; j++, inPolygon++){
			if (inPolygon->surf != inSurface)
				continue;

			if (inPolygon->type != ID_FACE){
				qprintf("WARNING: polygon type != ID_FACE, discarded...\n");
				continue;
			}

			if (inPolygon->nverts != 3){
				qprintf("WARNING: polygon has %i vertices, discarded...\n", inPolygon->nverts);
				continue;
			}

			for (k = 0, inPolVert = inPolygon->v; k < 3; k++, inPolVert++){
				inPoint = &inLayer->point.pt[inPolVert->index];

				vertex.xyz[0] = inPoint->pos[0];
				vertex.xyz[1] = inPoint->pos[2];
				vertex.xyz[2] = inPoint->pos[1];

				vertex.st[0] = vertex.xyz[defaultSTAxis[0]] * defaultXYZ2STScale[0];
				vertex.st[1] = vertex.xyz[defaultSTAxis[1]] * defaultXYZ2STScale[1];

				vertex.color[0] = inSurface->color.rgb[0] * inSurface->diffuse.val * 255;
				vertex.color[1] = inSurface->color.rgb[1] * inSurface->diffuse.val * 255;
				vertex.color[2] = inSurface->color.rgb[2] * inSurface->diffuse.val * 255;
				vertex.color[3] = 255;

				for (l = 0, inVMapPt = inPoint->vm; l < inPoint->nvmaps; l++, inVMapPt++){
					if (inVMapPt->vmap->type == LWID_('T', 'X', 'U', 'V')){
						vertex.st[0] = inVMapPt->vmap->val[inVMapPt->index][0];
						vertex.st[1] = 1.0f - inVMapPt->vmap->val[inVMapPt->index][1];
					}

					if (inVMapPt->vmap->type == LWID_('R', 'G', 'B', 'A')){
						vertex.color[0] = inVMapPt->vmap->val[inVMapPt->index][0] * inSurface->color.rgb[0] * inSurface->diffuse.val * 255;
						vertex.color[1] = inVMapPt->vmap->val[inVMapPt->index][1] * inSurface->color.rgb[1] * inSurface->diffuse.val * 255;
						vertex.color[2] = inVMapPt->vmap->val[inVMapPt->index][2] * inSurface->color.rgb[2] * inSurface->diffuse.val * 255;
						vertex.color[3] = inVMapPt->vmap->val[inVMapPt->index][3] * 255;
					}
				}

				for (l = 0, inVMapPt = inPolVert->vm; l < inPolVert->nvmaps; l++, inVMapPt++){
					if (inVMapPt->vmap->type == LWID_('T', 'X', 'U', 'V')){
						vertex.st[0] = inVMapPt->vmap->val[inVMapPt->index][0];
						vertex.st[1] = 1.0f - inVMapPt->vmap->val[inVMapPt->index][1];
					}

					if (inVMapPt->vmap->type == LWID_('R', 'G', 'B', 'A')){
						vertex.color[0] = inVMapPt->vmap->val[inVMapPt->index][0] * inSurface->color.rgb[0] * inSurface->diffuse.val * 255;
						vertex.color[1] = inVMapPt->vmap->val[inVMapPt->index][1] * inSurface->color.rgb[1] * inSurface->diffuse.val * 255;
						vertex.color[2] = inVMapPt->vmap->val[inVMapPt->index][2] * inSurface->color.rgb[2] * inSurface->diffuse.val * 255;
						vertex.color[3] = inVMapPt->vmap->val[inVMapPt->index][3] * 255;
					}
				}

				// Add it to the vertex list if not added yet
				if (numIndices == SHADER_MAX_INDEXES){
					printf("SHADER_MAX_INDEXES hit\n");
					return;
				}

				for (l = 0; l < numVertices; l++){
					if (vertexList[l].xyz[0] != vertex.xyz[0] || vertexList[l].xyz[1] != vertex.xyz[1] || vertexList[l].xyz[2] != vertex.xyz[2])
						continue;
					if (vertexList[i].st[0] != vertex.st[0] || vertexList[i].st[1] != vertex.st[1])
						continue;

					break;
				}

				if (l == numVertices){
					if (numVertices == SHADER_MAX_VERTEXES){
						printf("SHADER_MAX_VERTEXES hit\n");
						return qfalse;
					}

					indexList[numIndices++] = numVertices;
					vertexList[numVertices++] = vertex;
				}
				else
					indexList[numIndices++] = l;
			}
		}

		// Emit the indices
		fm->firstIndex[i] = numDrawIndexes;
		fm->numIndices[i] = numIndices;

		for (j = 0; j < numIndices; j += 3){
			if (numDrawIndexes + 3 > MAX_MAP_DRAW_INDEXES)
				Error("MAX_MAP_DRAW_INDEXES");

			drawIndexes[numDrawIndexes++] = indexList[j+0];
			drawIndexes[numDrawIndexes++] = indexList[j+1];
			drawIndexes[numDrawIndexes++] = indexList[j+2];
		}

		// Compute neighbors
		fm->firstNeighbor[i] = fm->firstIndex[i];

		if (numDrawNeighbors + fm->numIndices[i] > MAX_MAP_DRAW_NEIGHBORS)
			Error("MAX_MAP_DRAW_NEIGHBORS");

		BuildSurfaceTriangleNeighbors(fm->numIndices[i] / 3, &drawIndexes[fm->firstIndex[i]], &drawNeighbors[fm->firstNeighbor[i]]);
		numDrawNeighbors += fm->numIndices[i];

		for (j = 0; j < numVertices; j++){
			if (numDrawVerts == MAX_MAP_DRAW_VERTS)
				Error("MAX_MAP_DRAW_VERTS");

			outVert = &drawVerts[numDrawVerts++];

			outVert->xyz[0] = vertexList[j].xyz[0];
			outVert->xyz[1] = vertexList[j].xyz[1];
			outVert->xyz[2] = vertexList[j].xyz[2];

			outVert->st[0] = vertexList[j].st[0];
			outVert->st[1] = vertexList[j].st[1];

			outVert->color[0] = vertexList[j].color[0];
			outVert->color[1] = vertexList[j].color[1];
			outVert->color[2] = vertexList[j].color[2];
			outVert->color[3] = vertexList[j].color[3];
		}

		// Compute radius for culling
		fm->radius[i] = RadiusFromBounds(mins, maxs);

		// Compute face planes
		fm->firstFacePlane[i] = numFacePlanes;

		if (numFacePlanes + fm->numIndices[i]/3 > MAX_MAP_DRAW_FACEPLANES)
			Error("MAX_MAP_DRAW_FACEPLANES");

		CalcSurfaceFacePlanes(fm->numIndices[i] / 3, &drawIndexes[fm->firstIndex[i]], &facePlanes[fm->firstFacePlane[i]], &drawVerts[fm->firstVertex[i]]);
		numFacePlanes += fm->numIndices[i] / 3;

		// Compute tangent vectors
		CalcSurfaceTangentVectors(fm->numIndices[i], &drawIndexes[fm->firstIndex[i]], fm->numVertices[i], &drawVerts[fm->firstVertex[i]]);

		if (fm->numIndices[i] > SHADER_MAX_INDEXES || fm->numVertices[i] > SHADER_MAX_VERTEXES)
			Error("SHADER_MAX_INDEXES or SHADER_MAX_VERTEXES hit by foliage surface with shader %s", name);

		// Skip to next surface
		inSurface = inSurface->next;
	}

	lwFreeObject(inObject);

	return qtrue;
}

static foliageModel_t *EmitFoliageModel (const char *model){

	foliageModel_t	*fm;
	int				i;

	for (i = 0, fm = mapFoliageModels; i < numMapFoliageModels; i++, fm++){
		if (!Q_stricmp(fm->model, model))
			return fm;
	}

	if (numMapFoliageModels == MAX_FOLIAGE_MODELS)
		Error("MAX_FOLIAGEMODELS");

	fm = &mapFoliageModels[numMapFoliageModels];
	strcpy(fm->model, model);

	// Insert the model geometry into the BSP
	if (strstr(model, ".md3") || strstr(model, ".MD3")){
		if (!InsertMD3FoliageModel(fm))
			return NULL;
	}
	else if (strstr(model, ".ase") || strstr(model, ".ASE")){
		if (!InsertASEFoliageModel(fm))
			return NULL;
	}
	else if (strstr(model, ".lwo") || strstr(model, ".LWO")){
		if (!InsertLWOFoliageModel(fm))
			return NULL;
	}
	else
		return NULL;

	numMapFoliageModels++;
	return fm;
}


// =====================================================================


#define MAX_FOLIAGE_INSTANCES	32768

typedef struct {
	vec3_t		origin;
	vec3_t		angles;
} foliageInstance_t;

static int					numFoliageInstances;
static foliageInstance_t	foliageInstances[MAX_FOLIAGE_INSTANCES];


int M_RandInt (void){

	static unsigned	m_randSeed;

	return (((m_randSeed = m_randSeed * 214013 + 2531011) >> 16) & 0x7FFF);
}

static float Random (void){

	static qboolean	initialized = qfalse;

	if (!initialized){
		initialized = qtrue;

		srand(0);
	}

	return (float)rand() / RAND_MAX;
}

static void LerpFoliageVert( drawVertNew_t *a, drawVertNew_t *b, drawVertNew_t *out ) {

	out->xyz[0] = 0.5 * (a->xyz[0] + b->xyz[0]);
	out->xyz[1] = 0.5 * (a->xyz[1] + b->xyz[1]);
	out->xyz[2] = 0.5 * (a->xyz[2] + b->xyz[2]);

	out->normal[0] = 0.5 * (a->normal[0] + b->normal[0]);
	out->normal[1] = 0.5 * (a->normal[1] + b->normal[1]);
	out->normal[2] = 0.5 * (a->normal[2] + b->normal[2]);

	out->color[0] = (a->color[0] + b->color[0]) >> 1;
	out->color[1] = (a->color[1] + b->color[1]) >> 1;
	out->color[2] = (a->color[2] + b->color[2]) >> 1;
	out->color[3] = (a->color[3] + b->color[3]) >> 1;
}

static void SubdivideFoliageTriangle_r( foliage_t *foliage, drawVertNew_t **tri )
{
	drawVertNew_t	mid, *tri2[ 3 ];
	int				max;


	/* limit test */
	if( numFoliageInstances >= MAX_FOLIAGE_INSTANCES)
		return;
	
	/* plane test */
	{
		vec4_t		plane;
		
		
		/* make a plane */
		if( !PlaneFromPoints( plane, tri[ 0 ]->xyz, tri[ 1 ]->xyz, tri[ 2 ]->xyz ) )
			return;
		
		/* if normal is too far off vertical, then don't place an instance */
		if( plane[ 2 ] < 0.5f )
			return;
	}
	
	/* subdivide calc */
	{
		int					i;
		float				*a, *b, dx, dy, dz, dist, maxDist;
		foliageInstance_t	*fi;
		
		
		/* get instance */
		fi = &foliageInstances[ numFoliageInstances ];
		
		/* find the longest edge and split it */
		max = -1;
		maxDist = 0.0f;
		VectorClear( fi->origin );
		for( i = 0; i < 3; i++ )
		{
			/* get verts */
			a = tri[ i ]->xyz;
			b = tri[ (i + 1) % 3 ]->xyz;
			
			/* get dists */
			dx = a[ 0 ] - b[ 0 ];
			dy = a[ 1 ] - b[ 1 ];
			dz = a[ 2 ] - b[ 2 ];
			dist = (dx * dx) + (dy * dy) + (dz * dz);
			
			/* longer? */
			if( dist > maxDist )
			{
				maxDist = dist;
				max = i;
			}
			
			/* add to centroid */
			VectorAdd( fi->origin, tri[ i ]->xyz, fi->origin );
		}
		
		/* is the triangle small enough? */
		if( maxDist <= (foliage->density * foliage->density) )
		{
			float	alpha, odds, r;
			
			
			/* get average alpha */
			if( foliage->inverseAlpha == 2 )
				alpha = 1.0f;
			else
			{
				alpha = ((float) tri[ 0 ]->color[ 3 ] + (float) tri[ 1 ]->color[ 3 ] + (float) tri[ 2 ]->color[ 3 ]) / 765.0f;
				if( foliage->inverseAlpha == 1 )
					alpha = 1.0f - alpha;
				if( alpha < 0.75f )
					return;
			}
			
			/* roll the dice */
			odds = foliage->odds * alpha;
			r = Random();
			if( r > odds )
				return;
			
			/* scale centroid */
			VectorScale( fi->origin, 0.33333333f, fi->origin );

			fi->angles[0] = 0.0f;
			fi->angles[1] = (float)(M_RandInt() % 360);
			fi->angles[2] = 0.0f;

			/* add to count and return */
			numFoliageInstances++;
			return;
		}
	}
	
	/* split the longest edge and map it */
	LerpFoliageVert( tri[ max ], tri[ (max + 1) % 3 ], &mid );
	
	/* recurse to first triangle */
	VectorCopy( tri, tri2 );
	tri2[ max ] = &mid;
	SubdivideFoliageTriangle_r( foliage, tri2 );
	
	/* recurse to second triangle */
	VectorCopy( tri, tri2 );
	tri2[ (max + 1) % 3 ] = &mid;
	SubdivideFoliageTriangle_r( foliage, tri2 );
}

void AddFoliageToSurface (dsurface_t *surf, shaderInfo_t *si){

	foliage_t			*foliage;
	foliageModel_t		*fm;
	foliageInstance_t	*fi;
	dfoliage_t			*f;
	int					*indices;
	drawVertNew_t		*vertices, *tri[3];
	mapDrawSurface_t	*ds;
	int					i, j;

	if (!si || !si->foliage)
		return;

	indices = &drawIndexes[surf->firstIndex];
	vertices = &drawVerts[surf->firstVert];

	for (foliage = si->foliage; foliage; foliage = foliage->next){

		numFoliageInstances = 0;

		for (i = 0; i < surf->numIndexes; i += 3){
			tri[0] = &vertices[indices[i+0]];
			tri[1] = &vertices[indices[i+1]];
			tri[2] = &vertices[indices[i+2]];

			SubdivideFoliageTriangle_r(foliage, tri);
		}

		if (!numFoliageInstances)
			continue;

		// Emit the foliage model
		fm = EmitFoliageModel(foliage->model);
		if (!fm)
			continue;		// Model wasn't found

		// Add a foliage drawSurface for every model surface
		for (i = 0; i < fm->numSurfaces; i++){
			ds = AllocDrawSurf();

			ds->foliage = qtrue;
			ds->foliageShader = fm->shader[i];
			ds->foliageIndex = fm->firstIndex[i];
			ds->foliageVertex = fm->firstVertex[i];
			ds->foliageNeighbor = fm->firstNeighbor[i];
			ds->foliageFacePlane = fm->firstFacePlane[i];
			ds->foliageRadius = fm->radius[i];
			ds->foliageMinDistance = foliage->minDistance;
			ds->foliageMaxDistance = foliage->maxDistance;
			ds->firstFoliage = numFoliages;
			ds->numFoliages = numFoliageInstances;

			ds->shaderInfo = fm->shaderInfo[i];

			ds->numIndexes = fm->numIndices[i];
			ds->numVerts = fm->numVertices[i];

			// Emit the foliage instances
			for (j = 0, fi = foliageInstances; j < numFoliageInstances; j++, fi++){
				if (numFoliages == MAX_MAP_FOLIAGEINSTANCES)
					Error("MAX_MAP_FOLIAGEINSTANCES");

				f = &foliages[numFoliages++];

				VectorCopy(fi->origin, f->origin);
				VectorCopy(fi->angles, f->angles);
			}
		}
	}
}
